public class SubtreeAnotherTree {
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        if(root == null && subRoot != null || subRoot == null && root != null) {
            // 有一方为空, 说明不是相同的
            return false;
        }
        // 看根节点这棵树是否和 subRoot 相同
        if(isSameTree(root, subRoot)) {
            return true;
        }
        // 如果上面根节点的不相同, 再看左子树是否和 subRoot 相同
        if(isSubtree(root.left, subRoot)) {
            return true;
        }
        // 如果左子树不相同,看看右子树是否相同
        if(isSubtree(root.right, subRoot)) {
            return true;
        }
        // 如果上面都不相同
        return false;

        // 可以精简为下面这行代码
        // return isSameTree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }

    // 判断两棵树是否相同
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null) {
            return true;
        }
        if(p == null || q == null || p.val != q.val) {
            return false;
        }

        boolean left = isSameTree(p.left, q.left);
        boolean right = isSameTree(p.right, q.right);
        return left && right;
    }
}
